package com.LeetCode.temporaryTest.dp;

import org.junit.Test;

public class shares {
    /**
     * 买卖一次的情况
     */
    private int maxProfitInOneTime(int[] prices){
        int curMin = Integer.MAX_VALUE;
        int res = 0;
        for(int p : prices){
            curMin = Math.min(curMin, p);
            res = Math.max(res , p - curMin);
        }
        return res;
    }

    @Test
    public void testaxProfitInOneTimeM(){
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfitInOneTime(prices));
    }

    /**
     * 可以交易多次 -- dp解法
     */
    private int maxProfitInMostTimeSolveByDp(int[] prices){
        int len = prices.length;
        if(len == 0) return 0;
        // 第 i 天 是否持有
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for(int i = 1; i < len; i++){
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }

    /**
     * 贪心法解决 可交易多次的股票问题
     */
    private int maxProfitInMostTimeSolveBuGreedy(int[] prices){
        int res = 0;
        int len = prices.length;
        for(int i = 1; i<len; i++){
            res = prices[i] > prices[i-1] ? res + prices[i] - prices[i-1] : res;
        }
        return res;
    }

    @Test
    public void testMaxProfitInMostTime(){
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfitInMostTimeSolveByDp(prices));
        System.out.println(maxProfitInMostTimeSolveBuGreedy(prices));
    }

    /**
     * 可以交易两次的情况
     */
    private int maxProfitInTwoTime(int[] prices){
        int len = prices.length;
        if(len < 2) return 0;
        int max_k = 2;
        // 0 从未持有 1 第一次买入 2 第一次抛出 3 第二次买入 4 第二次抛出
        int[] dp = new int[5];
        dp[0] = 0;
        dp[1] = -prices[0];
        dp[2] = dp[3] = dp[4] = Integer.MIN_VALUE;
        for(int i = 1; i<len; i++){
            dp[1] = Math.max(dp[1] , dp[0] - prices[i]);
            dp[2] = Math.max(dp[2] , dp[1] + prices[i]);
            dp[3] = Math.max(dp[3] , dp[2] - prices[i]);
            dp[4] = Math.max(dp[4] , dp[3] + prices[i]);
        }
        return Math.max(dp[2] , dp[4]);
    }

    @Test
    public void testMaxProfitInTwoTime(){
        int[] prices = {3,3,5,0,0,3,1,4};
        System.out.println(maxProfitInTwoTime(prices));
    }

    /**
     * 指定可以交易 k 次
     */
    private int maxProfitInKTime(int[] prices , int k){
        int len = prices.length;
        if(k < 1) return 0;
        if(k > len / 2) return maxProfitInMostTimeSolveBuGreedy(prices);

        //第 几次 买还是不买
        int[][] dp = new int[k][2];

        for(int i=0; i<k; i++){
            dp[i][0] = Integer.MIN_VALUE;
        }

        for(int p : prices){
            dp[0][0] = Math.max(dp[0][0] , 0 - p);
            dp[0][1] = Math.max(dp[0][1] , dp[0][0] + p);
            for(int i=1; i<k; i++){
                dp[i][0] = Math.max(dp[i][0] , dp[i-1][1] - p);
                dp[i][1] = Math.max(dp[i][1] , dp[i][0] + p);
            }
        }
        return dp[k-1][1];
    }

    @Test
    public void testMaxProfieInKTime(){
        int[] prices = {3,2,6,5,0,3};
        System.out.println(maxProfitInKTime(prices,2));
    }

    /**
     * 包含一天冷冻期
     */
    private int maxProfitWithFreezingTime(int[] prices){
        int len = prices.length;
        if(len == 0) return 0;

        int[][] dp = new int[len][3];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for(int i=1; i<len; i++){
            dp[i][0] = Math.max(dp[i-1][2], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
            dp[i][2] = dp[i-1][1] + prices[i];
        }
        return Math.max(dp[len - 1][0] , dp[len - 1][2]);
    }

    @Test
    public void testMaxProfitWithFreezingTime(){
        int[] prices = {1,2,3,0,2};
        System.out.println(maxProfitWithFreezingTime(prices));
    }

    /**
     * 包含手续费
     */
    private int maxProfitWithServiceCharge(int[] prices , int fee){
        int len = prices.length;
        if(len == 0) return 0;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i=1; i<len; i++){
            dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] - prices[i]);
        }
        return dp[len-1][0];
    }

    /**
     * 优化空间复杂度
     */
    private int maxProfitWithServiceCharge_BetterSpaceUse(int[] prices , int fee){
        int len = prices.length;
        if(len == 0) return 0;
        int[] dp = new int[2];
        dp[1] = -prices[0];
        for(int i=1; i<len; i++){
            dp[0] = Math.max(dp[0] , dp[1] + prices[i] - fee);
            dp[1] = Math.max(dp[1] , dp[0] - prices[i]);
        }
        return dp[0];
    }

    @Test
    public void testMaxProfitWithServiceCharge(){
        int[] prices = {1, 3, 2, 8, 4, 9};
        int fee = 2;
        System.out.println(maxProfitWithServiceCharge(prices,fee));
        System.out.println(maxProfitWithServiceCharge_BetterSpaceUse(prices,fee));
    }
}
